package com.leetcode.周赛.第233场;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author: xiaomi
 * @date: 2021/3/21
 * @description: 5710. 积压订单中的订单总数
 * https://leetcode-cn.com/contest/weekly-contest-233/problems/number-of-orders-in-the-backlog/
 * https://leetcode-cn.com/problems/number-of-orders-in-the-backlog/
 */
public class B_5710_积压订单中的订单总数 {

	static B_5710_积压订单中的订单总数 action = new B_5710_积压订单中的订单总数();

	public static void main(String[] args) {
//		test1();
		test2();
	}

	static void test1() {
		int[][] orders = {{10, 5, 0}, {15, 2, 1}, {25, 1, 1}, {30, 4, 0}};
		int res = action.getNumberOfBacklogOrders(orders);
		System.out.println("res = " + res);
	}

	static void test2() {
		int[][] orders = {{7, 1000000000, 1}, {15, 3, 0}, {5, 999999995, 0}, {5, 1, 1}};
		int res = action.getNumberOfBacklogOrders(orders);
		System.out.println("res = " + res);
	}


	/**
	 * 题目描述太多，不想看。
	 * 但是看了以后，似乎没有啥绕弯的地方。
	 * 但是如果使用了 heap,那么就需要将订单一个一个添加，可能会超时。
	 * 于是考虑使用一个变量来统计堆顶元素的数量,但是其实需要考虑删除以后后序的数量；
	 * 那么，考虑 map + heap 的结构
	 * --
	 * 更简单的结构，可以使用 heap+ int[2] !!!
	 * @param orders
	 * @return
	 */
	public int getNumberOfBacklogOrders(int[][] orders) {
		//订单的数量
		int orderNum = orders.length;
		//采购订单中堆顶元素的堆积数量
		//long topBuyOrderNum = 0;
		HashMap<Integer, Long> buyOrderMap = new HashMap<>();
		//购买订单
		PriorityQueue<Integer> buyOrderBigHeap = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2 - o1;
			}
		});

		//销售订单中堆顶元素的堆积数量
		//long topSellOrderNum = 0;
		HashMap<Integer, Long> sellOrderMap = new HashMap<>();
		//销售订单
		PriorityQueue<Integer> sellOrderSmallHeap = new PriorityQueue<Integer>();
		for (int i = 0; i < orderNum; i++) {
			int price = orders[i][0];
			int amount = orders[i][1];
			int type = orders[i][2];

			//判断类型
			if (type == 0) {
				//采购订单
				//处理逻辑：
				while (!sellOrderSmallHeap.isEmpty() && amount > 0 && sellOrderSmallHeap.peek() <= price) {
					//符合条件
					int topPrice = sellOrderSmallHeap.peek();
					long leftNum = sellOrderMap.get(topPrice);
					if (amount < leftNum) {
						//如果堆顶的数量仍然有剩余
						sellOrderMap.put(topPrice, leftNum - amount);
						amount = 0;
					} else {
						amount -= leftNum;
						sellOrderMap.remove(topPrice);
						sellOrderSmallHeap.poll();
					}
				}
				if (amount > 0) {
					if (buyOrderMap.containsKey(price)) {
						buyOrderMap.put(price, buyOrderMap.get(price) + amount);
					} else {
						buyOrderMap.put(price, (long) amount);
						buyOrderBigHeap.add(price);
					}
				}
			} else {
				//销售订单
				//处理逻辑：
				while (!buyOrderBigHeap.isEmpty() && amount > 0 && buyOrderBigHeap.peek() >= price) {
					//符合条件
					int topPrice = buyOrderBigHeap.peek();
					long leftNum = buyOrderMap.get(topPrice);
					if (amount < leftNum) {
						//如果堆顶的数量仍然有剩余
						buyOrderMap.put(topPrice, leftNum - amount);
						amount = 0;
					} else {
						amount -= leftNum;
						buyOrderMap.remove(topPrice);
						buyOrderBigHeap.poll();
					}
				}
				if (amount > 0) {
					//此时发生了积压
					if (sellOrderMap.containsKey(price)) {
						sellOrderMap.put(price, sellOrderMap.get(price) + amount);
					} else {
						sellOrderMap.put(price, (long) amount);
						sellOrderSmallHeap.add(price);
					}
				}
			}
		}

		//最后统计 两个 map 的数量
		long res = 0;
		for (Map.Entry<Integer, Long> entry :
				buyOrderMap.entrySet()) {
			res += entry.getValue();
		}
		for (Map.Entry<Integer, Long> entry :
				sellOrderMap.entrySet()) {
			res += entry.getValue();
		}
		return (int) (res % (1_000_000_007));
	}
}
